The file of this patent application includes a CD-ROM with a file named APPENDIX A.TXT, created Dec. 17, 2002, and having a size of 28,012 bytes, which is incorporated by reference. This file contains computer program listings referred to as Appendices A. Appendix A is a software program embodying aspects of the present invention. These programs were written for Microsoft Windows. Appendix A is a program that describes the geometric skeleton of a polygonal shape with respect to one of its sides according to the present invention.
This patent specification contains material that is subject to copyright protection. The copyright owner has no objection to the reproduction of this patent specification or related materials from associated patent office files for the purposes of review, but otherwise reserves all copyright whatsoever.
The present invention relates to polygons in general and in particular to the generation of geometric skeletons of polygonal shapes, such as character font outlines and shapes.
The generation of a geometric skeleton is an important step in many image-processing tasks such as offset generation, character stroke generation, and artistic effects. For example, in character stroke generation, the geometric skeleton provides a medial axis transform associating points on the boundary with corresponding points on the other side of the stroke.
The publication xe2x80x9cMedial Axis Transformation of a Planar Shapexe2x80x9d, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAM1-4, No. 4, July 1982, by D. T. Lee (hereinafter called Lee) discloses a method for computing a medial axis of a planar shape represented by an n-edge polygon. Lee defines the transformation as follows: given an object represented, say by a simple polygon G, the medial axis is the set of points {q} internal to G such that there are least two points on the object""s boundary that are equidistant from {q} and are closest to {q}. Because of its shape, the medial axis of a figure is also called the skeleton or the symmetric axis of the figure. Specifically, Lee defines the skeleton Sp for a polygonal shape P as a set of edges and nodes, where the edges are of the form of loci, and the nodes are the intersections points of these loci (locations in Sp that are closest to more than two points in P). The skeleton of a polygon is described in Lee as being made up of three types of loci. Namely, (1) the locus between two line segments, which is in this case a line segment, (2) the locus between a point and a line segment, which is in this case a parabolic segment, (3) the locus between two points, which is in this case a line. This method suffers from errors in calculating the skeleton, due to errors in floating point calculations, especially in calculating (2) above. Consequently, it is not possible to accurately describe a geometric skeleton in this fashion.
It is an object of the present invention to ameliorate one or more disadvantages of the prior art.
According to one aspect of the invention, there is provided a method of generating a component of a geometric skeleton of a polygon, said polygon comprising a plurality of interconnected line segments, the method comprising the step of: determining, for a current line segment of said plurality, a first point on a line perpendicular to said current line segment at a second point corresponding to a parameter value, wherein said first point is a point of a locus between said current line segment and one other of said line segments, which locus point is the closest locus point, on said line, to the current line segment of any locus point of said current line segment and any one of the line segments other than the current line segment, said first point forming a point of said component of said skeleton.
According to another aspect of the invention, there is provided a method of generating components of a geometric skeleton of a polygon, wherein said polygon comprises a plurality of line segments and one or more concave vertices, the method comprising the step of: determining, for each said concave vertex, a first point on a radial line from the current concave vertex, wherein said radial line has a corresponding parameter value and said first point is a point of a locus between said current concave vertex and a said line segment, which locus point is the closest locus point on said radial line of any locus point of said current concave vertex and any one of said line segments, said first point forming a point of said components of said skeleton.
According to still another aspect of the invention, there is provided a method of generating a geometric skeleton of a polygonal shape, the method comprising the steps of: determining a parameter value of an edge or concave vertex of the polygonal shape where the distance from said edge or concave vertex to a point of a locus between said edge or concave vertex and another edge of the polygonal shape is a minimum; and storing said parameter value and a label representative of said another edge having said minimum distance as a data signal representative of the geometric skeleton at said parameter value.
According to still another aspect of the invention, there is provided a method of generating a representation of components of a geometric skeleton of a polygon, wherein the polygon comprises a plurality of line segments, the method comprising the steps of: generating, for each said line segment (i) of the polygon, a list comprising a plurality of members { . . . ,(txe2x80x2,N), . . . ,(txe2x80x3,P), . . . }, where (txe2x80x2,N) and (txe2x80x3,P) are any members of the list, txe2x80x2 and txe2x80x3 are parameter values of a current line segment (i) and which are adjacent parameter values in the list, and N and P are said line segments of the polygon other than the current line segment (i), whereby a point of locus(i,N) on a line perpendicular to the current line segment (i) at the parameter value txe2x80x2 forms one point of the skeleton and a point of locus(i,P) on a line perpendicular to the current line segment (i) at the parameter value txe2x80x3 forms another point of the skeleton, and for any parameter value txe2x80x2xe2x80x3 immediate txe2x80x2 and txe2x80x3 a point, being one of a point of locus (i,N) or a point of locus(i,P) on the line perpendicular to the current line segment (i) at the parameter value txe2x80x2xe2x80x3, which is closest to the current line segment (i) forms another point of the skeleton; and storing said lists as a representation of said components of said skeleton.
According to still another aspect of the invention, there is provided a method of generating a representation of components of a geometric skeleton of a polygon, wherein the polygon comprises a plurality of line segments and one or more concave vertices, the method comprising the steps of: generating, for each concave vertex (i) of the polygon, a list comprising a plurality of members { . . . ,(xcex8xe2x80x2,N), . . . ,(xcex8xe2x80x3,P), . . . }, where (xcex8xe2x80x2,N) and (xcex8xe2x80x3,P) are any members of the list, xcex8xe2x80x2 and xcex8xe2x80x3 are parameter values of a current concave vertex (i) and which are adjacent parameter values in the list, and N and P are said line segments of the polygon, whereby a point of locus(i,N) on a radial line from the current concave vertex (i) at the parameter value xcex8xe2x80x2 forms one point of the skeleton and a point of locus(i,P) on a radial line from the current concave vertex (i) at the parameter value xcex8xe2x80x3 forms another point of the skeleton, and for any parameter value xcex8xe2x80x2xe2x80x3 immediate xcex8xe2x80x2 and xcex8xe2x80x3 a point, being one of a point of locus (i,N) or a point of locus(i,P) on the radial line from the current concave vertex (i) at the parameter value xcex8xe2x80x2xe2x80x3, which is closest to the current concave vertex (i) forms another point of the skeleton; and storing said lists as a representation of said components of said skeleton.
According to still another aspect of the invention, there is provided a method of generating a representation of a geometric skeleton of a polygon, wherein the polygon comprises a plurality of line segments, the method comprising the steps of: generating, for each said line segment (i) of the polygon, a list comprising a plurality of members { . . . ,(txe2x80x2, N), . . . ,(txe2x80x3,P), . . . }, where (txe2x80x2,N) and (txe2x80x3,P) are any members of the list, txe2x80x2 and txe2x80x3 are parameter values of a current line segment (i) and which are adjacent parameter values in the list, and N and P are said line segments of the polygon other than the current line segment (i), whereby a point of locus(i,N) on a line perpendicular to the current line segment (i) at the parameter value txe2x80x2 forms one point of the skeleton and a point of locus(i,P) on a line perpendicular to the current line segment (i) at the parameter value txe2x80x3 forms another point of the skeleton, and for any parameter value txe2x80x2xe2x80x3 immediate txe2x80x2 and txe2x80x3 a point, being one of a point of locus (i,N) or a point of locus(i,P) on the line perpendicular to the current line segment (i) at the parameter value txe2x80x2xe2x80x3, which is closest to the current line segment (i) forms another point of the skeleton; generating, for each concave vertex (i) of the polygon if any, a list comprising a plurality of members { . . . ,(xcex8xe2x80x2,N), . . . , (xcex8xe2x80x3,P), . . . }, where (xcex8xe2x80x2,N) and (xcex8xe2x80x3,P) are any members of the list, xcex8xe2x80x2 and xcex8xe2x80x3 are parameter values of a current concave vertex (i) and which are adjacent parameter values in the list, and N and P are said line segments of the polygon, whereby a point of locus(i,N) on a radial line from the current concave vertex (i) at the parameter value xcex8xe2x80x2 forms one point of the skeleton and a point of locus(i,P) on a radial line from the current concave vertex (i) at the parameter value xcex8xe2x80x3 forms another point of the skeleton, and for any parameter value xcex8xe2x80x2xe2x80x3 immediate xcex8xe2x80x2 and xcex8xe2x80x3 a point, being one of a point of locus (i,N) or a point of locus(i,P) on the radial line from the current concave vertex (i) at the parameter value xcex8xe2x80x2xe2x80x3, which is closest to the current concave vertex (i) forms another point of the skeleton; and storing said lists as a representation of said skeleton.
According to still another aspect of the invention, there is provided a method of generating a representation of skeletal components of a polygon, the method comprising the steps of: (a) selecting a first edge Ni of the polygon; (b) creating a list associated with said first edge for storing k members (tk,Nk), where tk is a parameter value associated with a point on said first edge, and Nk is an edge of the polygon; (c) selecting a second edge Nj of the polygon other than the first edge Ni; (d) determining at least one said parameter value on said first edge Ni so that a locus(Ni,Nj) distance function is monotonic moving away from said at least one parameter value; (e) adding said determined parameter value to said list if not already on said list; (f) determining, for each two members of the list (tk,Nk), (tk+1, Nk+1) having adjacent parameter values, if a point of locus(Ni,Nj) is closer to the first edge than either of a point of locus(Ni,Nk) and a point of locus(Ni,Nk+1) at any parameter value intermediate tk and tk+1; (g) adding said determined intermediate parameter value to said list, if not already on said list; (h) replacing any existing member (tk,Nk) of the list with the member (tk,Nj) if the locus (Ni, Nj) distance function is less than the locus (Ni,Nk) distance function at the parameter value tk; (i) repeating steps (c) to (h) for each remaining said second edge; (j) repeating steps (a) to (i) for each remaining said first edge; and (k) storing said lists as a data signal representative of said skeletal components.
According to still another aspect of the invention, there is provided a method of generating a representation of skeletal components of a polygon, the method comprising the steps of: (a) selecting a first concave vertex Vi of the polygon; (b) creating a list associated with said first concave vertex for storing k members (tk,Nk), where tk is a parameter value associated with a radial line from said first concave vertex, and Nk is an edge of the polygon; (c) selecting a second edge Nj of the polygon; (d) determining at least one said parameter value associated with said first concave vertex Vi so that a locus(Vi,Nj) distance function is monotonic moving away from said at least one parameter value; (e) adding said determined parameter value to said list if not already on said list; (f) determining, for each two members of the list (tk,Nk), (tk+1, Nk+1) having adjacent parameter values, if a point of locus(Vi,Nj) is closer to the first concave vertex than either of a point of locus(Vi,Nk) and a point of locus(Vi,Nk+1) at any parameter value intermediate tk and tk+1; (g) adding said determined intermediate parameter value to said list, if not already on said list; (h) replacing any existing member (tk,Nk) of the list with the member (tk,Nj) if the locus (Vi,Nj) distance function is less than the locus (Vi, Nk) distance function at the parameter value tk; (i) repeating steps (c) to (h) for each remaining said second edge; (j) repeating steps (a) to (i) for each remaining said first concave vertices; and (k) storing said lists as a data signal representative of said skeletal components.
According to still another aspect of the invention, there is provided apparatus for generating a component of a geometric skeleton of a polygon, said polygon comprising a plurality of interconnected line segments, the apparatus comprising: means for determining, for a current line segment of said purality, a first point on a line perpendicular to said current line segment at a second point corresponding to a parameter value, wherein said first point is a point of a locus between said current line segment and one other of said line segments, which locus point is the closest locus point, on said line, to the current line segment of any locus point of said current line segment and any one of the line segments other than the current line segment, said first point forming a point of said component of said skeleton.
According to still another aspect of the invention, there is provided apparatus for generating components of a geometric skeleton of a polygon, wherein said polygon comprises a plurality of line segments and one or more concave vertices, the apparatus comprising: means for determining, for each said concave vertex, a first point on a radial line from the current concave vertex, wherein said radial line has a corresponding parameter value and said first point is a point of a locus between said current concave vertex and a said line segment, which locus point is the closest locus point on said radial line of any locus point of said current concave vertex and any one of said line segments, said first point forming a point of said components of said skeleton.
According to still another aspect of the invention, there is provided apparatus for generating a representation of components of a geometric skeleton of a polygon, wherein the polygon comprises a plurality of line segments, the apparatus comprising: means for generating, for each said line segment (i) of the polygon, a list comprising a plurality of members { . . . ,(txe2x80x2,N), . . . ,(txe2x80x3,P), . . . }, where (txe2x80x2,N) and (txe2x80x3,P) are any members of the list, txe2x80x2 and txe2x80x3 are parameter values of a current line segment (i) and which are adjacent parameter values in the list, and N and P are said line segments of the polygon other than the current line segment (i), whereby a point of locus(i,N) on a line perpendicular to the current line segment (i) at the parameter value txe2x80x2 forms one point of the skeleton and a point of locus(i,P) on a line perpendicular to the current line segment (i) at the parameter value txe2x80x3 forms another point of the skeleton, and for any parameter value txe2x80x2xe2x80x3 immediate txe2x80x2 and txe2x80x3 a point, being one of a point of locus (i,N) or a point of locus(i,P) on the line perpendicular to the current line segment (i) at the parameter value txe2x80x2xe2x80x3, which is closest to the current line segment (i) forms another point of the skeleton; and means for storing said lists as a representation of said components of said skeleton.
According to still another aspect of the invention, there is provided apparatus for generating a representation of components of a geometric skeleton of a polygon, wherein the polygon comprises a plurality of line segments and one or more concave vertices, the apparatus comprising: means for generating, for each concave vertex (i) of the polygon, a list comprising a plurality of members { . . . ,(xcex8xe2x80x2,N), . . . ,(xcex8xe2x80x3,P), . . . }, where (xcex8xe2x80x2,N) and (xcex8xe2x80x3,P) are any members of the list, xcex8xe2x80x2 and xcex8xe2x80x3 are parameter values of a current concave vertex (i) and which are adjacent parameter values in the list, and N and P are said line segments of the polygon, whereby a point of locus(i,N) on a radial line from the current concave vertex (i) at the parameter value xcex8xe2x80x2 forms one point of the skeleton and a point of locus(i,P) on a radial line from the current concave vertex (i) at the parameter value xcex8xe2x80x3 forms another point of the skeleton, and for any parameter value xcex8xe2x80x2xe2x80x3 immediate xcex8xe2x80x2 and xcex8xe2x80x3 a point, being one of a point of locus (i,N) or a point of locus(i,P) on the radial line from the current concave vertex (i) at the parameter value xcex8xe2x80x2xe2x80x3, which is closest to the current concave vertex (i) forms another point of the skeleton; and means for storing said lists as a representation of said components of said skeleton.
According to still another aspect of the invention, there is provided apparatus for generating a representation of a geometric skeleton of a polygon, wherein the polygon comprises a plurality of line segments, the apparatus comprising: means for generating, for each said line segment (i) of the polygon, a list comprising a plurality of members { . . . ,(txe2x80x2,N), . . . ,(txe2x80x3,P), . . . }, where (txe2x80x2,N) and (txe2x80x3,P) are any members of the list, txe2x80x2 and txe2x80x3 are parameter values of a current line segment (i) and which are adjacent parameter values in the list, and N and P are said line segments of the polygon other than the current line segment (i), whereby a point of locus(i,N) on a line perpendicular to the current line segment (i) at the parameter value txe2x80x2 forms one point of the skeleton and a point of locus(i,P) on a line perpendicular to the current line segment (i) at the parameter value txe2x80x3 forms another point of the skeleton, and for any parameter value txe2x80x2xe2x80x3 immediate txe2x80x2 and txe2x80x3 a point, being one of a point of locus (i,N) or a point of locus(i,P) on the line perpendicular to the current line segment (i) at the parameter value txe2x80x2xe2x80x3, which is closest to the current line segment (i) forms another point of the skeleton; means for generating, for each concave vertex (i) of the polygon if any, a list comprising a plurality of members { . . . ,(xcex8xe2x80x2, N), . . . ,(xcex8xe2x80x3,P), . . . }, where (xcex8xe2x80x2,N) and (xcex8xe2x80x3,P) are any members of the list, xcex8xe2x80x2 and xcex8xe2x80x3 are parameter values of a current concave vertex (i) and which are adjacent parameter values in the list, and N and P are said line segments of the polygon, whereby a point of locus(i,N) on a radial line from the current concave vertex (i) at the parameter value xcex8xe2x80x2 forms one point of the skeleton and a point of locus(i,P) on a radial line from the current concave vertex (i) at the parameter value xcex8xe2x80x3 forms another point of the skeleton, and for any parameter value xcex8xe2x80x2xe2x80x3 immediate xcex8xe2x80x2 and xcex8xe2x80x3 a point, being one of a point of locus (i,N) or a point of locus(i,P) on the radial line from the current concave vertex (i) at the parameter value xcex8xe2x80x2xe2x80x3, which is closest to the current concave vertex (i) forms another point of the skeleton; and means for storing said lists as a representation of said skeleton.
According to still another aspect of the invention, there is provided apparatus for generating a representation of skeletal components of a polygon, the apparatus comprising: first selection means for selecting a first edge Ni of the polygon; creation means for creating a list associated with said first edge for storing k members (tk,Nk), where tk is a parameter value associated with a point on said first edge, and Nk is an edge of the polygon; second selection means for selecting a second edge Nj of the polygon other than the first edge Ni; first determination means for determining at least one said parameter value on said first edge Ni so that a locus(Ni,Nj) distance function is monotonic moving away from said at least one parameter value; first addition means for adding said determined parameter value to said list if not already on said list; second determination means for determining, for each two members of the list (tk,Nk), (tk+1, Nk+1) having adjacent parameter values, if a point of locus(Ni,Nj) is closer to the first edge than either of a point of locus(Ni,Nk) and a point of locus(Ni,Nk+1) at any parameter value intermediate tk and tk+1; second addition means for adding said determined intermediate parameter value to said list, if not already on said list; replacement means for replacing any existing member (tk,Nk) of the list with the member (tk,Nj) if the locus (Ni, Nj) distance function is less than the locus (Ni,Nk) distance function at the parameter value tk; first repetition means for repeating the operations of the second selection means, first determining means, first addition means, second determination means, second addition means, and replacement means for each remaining said second edge; second repetition means for repeating the operations of the first selection means, creation means, second selection means, first determination means, first addition means, second determination means, second addition means, replacement means, and first repetition means for each remaining said first edge; and storage means for storing said lists as a data signal representative of said skeletal components.
According to still another aspect of the invention, there is provided apparatus for generating a representation of skeletal components of a polygon, the apparatus comprising: first selection means for selecting a first concave vertex Vi of the polygon; creation means for creating a list associated with said first concave vertex for storing k members (tk,Nk), where tk is a parameter value associated with a radial line from said first concave vertex, and Nk is an edge of the polygon; second selection means for selecting a second edge Nj of the polygon; first determination means for determining at least one said parameter value associated with said first concave vertex Vi so that a locus(Vi,Nj) distance function is monotonic moving away from said at least one parameter value; first addition means for adding said determined parameter value to said list if not already on said list; second determination means for determining, for each two members of the list (tk,Nk), (tk+1, Nk+1having adjacent parameter values, if a point of locus(Vi,Nj) is closer to the first concave vertex than either of a point of locus(Vi,Nk) and a point of locus(Vi,Nk+1) at any parameter value intermediate tk and tk+1; second addition means for adding said determined intermediate parameter value to said list, if not already on said list; replacement means for replacing any existing member (tk,Nk) of the list with the member (tk,Nj) if the locus (Vi,Nj) distance function is less than the locus (Vi,Nk) distance function at the parameter value tk; first repetition means for repeating the operations of the second selection means, first determining means, first addition means, second determination means, second addition means, and replacement means for each remaining said second edge; second repetition means for repeating the operations of the first selection means, creation means, second selection means, first determination means, first addition means, second determination means, second addition means, replacement means, and first repetition means for each remaining said first concave vertices; and storage means for storing said lists as a data signal representative of said skeletal components.
According to still another aspect of the invention, there is provided a computer program product having a computer readable medium comprising a computer program for generating a component of a geometric skeleton of a polygon, said polygon comprising a plurality of interconnected line segments, the apparatus comprising: means for determining, for a current line segment of said purality, a first point on a line perpendicular to said current line segment at a second point corresponding to a parameter value, wherein said first point is a point of a locus between said current line segment and one other of said line segments, which locus point is the closest locus point, on said line, to the current line segment of any locus point of said current line segment and any one of the line segments other than the current line segment, said first point forming a point of said component of said skeleton.
According to still another aspect of the invention, there is provided a computer program product having a computer readable medium comprising a computer program for generating components of a geometric skeleton of a polygon, wherein said polygon comprises a plurality of line segments and one or more concave vertices, the computer program product comprising: means for determining, for each said concave vertex, a first point on a radial line from the current concave vertex, wherein said radial line has a corresponding parameter value and said first point is a point of a locus between said current concave vertex and a said line segment, which locus point is the closest locus point on said radial line of any locus point of said current concave vertex and any one of said line segments, said first point forming a point of said components of said skeleton.
According to still another aspect of the invention, there is provided a computer program product having a computer readable medium comprising a computer program for generating a representation of components of a geometric skeleton of a polygon, wherein the polygon comprises a plurality of line segments, the computer program product comprising:means for generating, for each said line segment (i) of the polygon, a list comprising a plurality of members { . . . ,(txe2x80x2,N), . . . ,(txe2x80x3,P), . . . }, where (txe2x80x2,N) and (txe2x80x3,P) are any members of the list, txe2x80x2 and txe2x80x3 are parameter values of a current line segment (i) and which are adjacent parameter values in the list, and N and P are said line segments of the polygon other than the current line segment (i), whereby a point of locus(i,N) on a line perpendicular to the current line segment (i) at the parameter value txe2x80x2 forms one point of the skeleton and a point of locus(i,P) on a line perpendicular to the current line segment (i) at the parameter value txe2x80x2 forms another point of the skeleton, and for any parameter value txe2x80x2xe2x80x3 immediate txe2x80x2 and txe2x80x3 a point, being one of a point of locus (i,N) or a point of locus(i,P) on the line perpendicular to the current line segment (i) at the parameter value txe2x80x2xe2x80x3, which is closest to the current line segment (i) forms another point of the skeleton; and means for storing said lists as a representation of said components of said skeleton.
According to still another aspect of the invention, there is provided a computer program product having a computer readable medium comprising a computer program for generating a representation of components of a geometric skeleton of a polygon, wherein the polygon comprises a plurality of line segments and one or more concave vertices, the computer program product comprising: means for generating, for each concave vertex (i) of the polygon, a list comprising a plurality of members { . . . ,(xcex8xe2x80x2,N), . . . ,(xcex8xe2x80x3,P), . . . }, where (xcex8xe2x80x2,N) and (xcex8xe2x80x3,P) are any members of the list, xcex8xe2x80x2 and xcex8xe2x80x3 are parameter values of a current concave vertex (i) and which are adjacent parameter values in the list, and N and P are said line segments of the polygon, whereby a point of locus(i,N) on a radial line from the current concave vertex (i) at the parameter value xcex8xe2x80x2 forms one point of the skeleton and a point of locus(i,P) on a radial line from the current concave vertex (i) at the parameter value xcex8xe2x80x3 forms another point of the skeleton, and for any parameter value xcex8xe2x80x2xe2x80x3 immediate xcex8xe2x80x2 and xcex8xe2x80x3 a point, being one of a point of locus (i,N) or a point of locus(i,P) on the radial line from the current concave vertex (i) at the parameter value xcex8xe2x80x2xe2x80x3, which is closest to the current concave vertex (i) forms another point of the skeleton; and means for storing said lists as a representation of said components of said skeleton.
According to still another aspect of the invention, there is provided a computer program product having a computer readable medium comprising a computer program for generating a representation of a geometric skeleton of a polygon, wherein the polygon comprises a plurality of line segments, the computer program product comprising: means for generating, for each said line segment (i) of the polygon, a list comprising a plurality of members { . . . ,(txe2x80x2,N), . . . ,(txe2x80x2,P), . . . }, where (txe2x80x2,N) and (txe2x80x3,P) are any members of the list, txe2x80x2 and txe2x80x3 are parameter values of a current line segment (i) and which are adjacent parameter values in the list, and N and P are said line segments of the polygon other than the current line segment (i), whereby a point of locus(i,N) on a line perpendicular to the current line segment (i) at the parameter value txe2x80x2 forms one point of the skeleton and a point of locus(i,P) on a line perpendicular to the current line segment (i) at the parameter value txe2x80x3 forms another point of the skeleton, and for any parameter value txe2x80x2xe2x80x3 immediate txe2x80x2 and txe2x80x3 a point, being one of a point of locus (i,N) or a point of locus(i,P) on the line perpendicular to the current line segment (i) at the parameter value txe2x80x2xe2x80x3, which is closest to the current line segment (i) forms another point of the skeleton; means for generating, for each concave vertex (i) of the polygon if any, a list comprising a plurality of members { . . . ,(xcex8xe2x80x2,N), . . . ,( xcex8xe2x80x3,P), . . . }, where (xcex8xe2x80x2,N) and (xcex8xe2x80x3,P) are any members of the list, xcex8xe2x80x2 and xcex8xe2x80x3 are parameter values of a current concave vertex (i) and which are adjacent parameter values in the list, and N and P are said line segments of the polygon, whereby a point of locus(i,N) on a radial line from the current concave vertex (i) at the parameter value xcex8xe2x80x2 forms one point of the skeleton and a point of locus(i,P) on a radial line from the current concave vertex (i) at the parameter value xcex8xe2x80x3 forms another point of the skeleton, and for any parameter value xcex8xe2x80x2xe2x80x3 immediate xcex8xe2x80x2 and xcex8xe2x80x3 a point, being one of a point of locus (i,N) or a point of locus(i,P) on the radial line from the current concave vertex (i) at the parameter value xcex8xe2x80x2xe2x80x3, which is closest to the current concave vertex (i) forms another point of the skeleton; and means for storing said lists as a representation of said skeleton.
According to still another aspect of the invention, there is provided a computer program product having a computer readable medium comprising a computer program for generating a representation of skeletal components of a polygon, the computer program product comprising: first selection means for selecting a first edge Ni of the polygon; creation means for creating a list associated with said first edge for storing k members (tk, Nk), where tk is a parameter value associated with a point on said first edge, and Nk is an edge of the polygon; second selection means for selecting a second edge Nj of the polygon other than the first edge Ni; first determination means for determining at least one said parameter value on said first edge Ni so that a locus(Ni,Nj) distance function is monotonic moving away from said at least one parameter value; first addition means for adding said determined parameter value to said list if not already on said list; second determination means for determining, for each two members of the list (tk,Nk), (tk+1, Nk+1) having adjacent parameter values, if a point of locus(Ni,Nj) is closer to the first edge than either of a point of locus(Ni,Nk) and a point of locus(Ni,Nk+1) at any parameter value intermediate tk and tk+1; second addition means for adding said determined intermediate parameter value to said list, if not already on said list; replacement means for replacing any existing member (tk,Nk) of the list with the member (tk,Nj) if the locus (Ni, Nj) distance function is less than the locus (Ni,Nk) distance function at the parameter value tk; first repetition means for repeating the operations of the second selection means, first determining means, first addition means, second determination means, second addition means, and replacement means for each remaining said second edge; second repetition means for repeating the operations of the first selection means, creation means, second selection means, first determination means, first addition means, second determination means, second addition means, replacement means, and first repetition means for each remaining said first edge; and storage means for storing said lists as a data signal representative of said skeletal components.
According to still another aspect of the invention, there is provided a computer program product having a computer readable medium comprising a computer program for generating a representation of skeletal components of a polygon, the computer program product comprising: first selection means for selecting a first concave vertex Vi of the polygon; creation means for creating a list associated with said first concave vertex for storing k members (tk,Nk), where tk is a parameter value associated with a radial line from said first concave vertex, and Nk is an edge of the polygon; second selection means for selecting a second edge Nj of the polygon; first determination means for determining at least one said parameter value associated with said first concave vertex Vi so that a locus(Vi,Nj) distance function is monotonic moving away from said at least one parameter value; first addition means for adding said determined parameter value to said list if not already on said list; second determination means for determining, for each two members of the list (tk,Nk), (tk+1, Nk+1) having adjacent parameter values, if a point of locus(Vi,Nj) is closer to the first concave vertex than either of a point of locus(Vi,Nk) and a point of locus(Vi,Nk+1) at any parameter value intermediate tk and tk+1; second addition means for adding said determined intermediate parameter value to said list, if not already on said list; replacement means for replacing any existing member (tk,Nk) of the list with the member (tk,Nj) if the locus (Vi,Nj) distance function is less than the locus (Vi,Nk) distance function at the parameter value tk; first repetition means for repeating the operations of the second selection means, first determining means, first addition means, second determination means, second addition means, and replacement means for each remaining said second edge; second repetition means for repeating the operations of the first selection means, creation means, second selection means, first determination means, first addition means, second determination means, second addition means, replacement means, and fist repetition means for each remaining said first concave vertices; and storage means for storing said lists as a data signal representative of said skeletal components.